package com.xk._02算法篇._01sort.sort.cmp;

import com.xk._02算法篇._01sort.sort.Sort;
import com.xk.tools.Integers;

/**
 * @description: 插入排序
 * @author: xu
 * @date: 2022/10/1 23:08
 */
public class InsertionSort1<E extends Comparable<E>> extends Sort<E> {
    /**
     * 插入排序
     */
    private void insertionSort1(){
        for (int begin = 1; begin < array.length; begin++) {
            int curIndex = begin;
            while (curIndex > 0 && cmp(curIndex-1, curIndex) > 0) {
                swap(curIndex, curIndex-1);
                curIndex--;
            }
        }
    }

    @Override
    protected void sort() {
        insertionSort1();
    }

    public static void main(String[] args) {
        Integer[] array = Integers.random(20, 1, 100);
        Integers.println(array);

        Sort<Integer> insertionSort1 = new InsertionSort1<>();
        insertionSort1.sort(array);
        Integers.println(array);
        System.out.println(insertionSort1);
    }
}
